#include <stdio.h>
#include <malloc.h>

struct BTNode
{
    char data;
    struct BTNode *pLchild; //左孩子指针
    struct BTNode *pRchild;
};

/*
函数声明
*/
struct BTNode *creatBTree(void);
void PreTraverseBTree(struct BTNode *pT);
void InTraverseBTree(struct BTNode *pT);
void PostTraverseBTree(struct BTNode *pT);

/*
主函数
*/
int main(void)
{

    struct BTNode *pT = creatBTree(); //内部动态构造一个链式二叉树，并返回根节点的地址
                                      //（因为根节点本身可能很大，但是根节点的地址在4G内存大小下，只占32位，即4个字节）
    printf("先序遍历：\n");
    PreTraverseBTree(pT); //先序遍历

    printf("中序遍历：\n");
    InTraverseBTree(pT); //中序遍历

    printf("后序遍历：\n");
    PostTraverseBTree(pT); //后序遍历

    return 0;
}

/*
静态构造一个二叉树，并返回根节点的地址
*/
struct BTNode *creatBTree(void)
{
    struct BTNode *pA = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode *pB = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode *pC = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode *pD = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode *pE = (struct BTNode *)malloc(sizeof(struct BTNode));

    pA->data = 'A';
    pB->data = 'B';
    pC->data = 'C';
    pD->data = 'D';
    pE->data = 'E';

    pA->pLchild = pB;
    pA->pRchild = pC;
    pB->pLchild = pB->pRchild = NULL;
    pC->pLchild = pD;
    pC->pRchild = NULL;
    pD->pLchild = NULL;
    pD->pRchild = pE;
    pE->pLchild = pE->pRchild = NULL;

    return pA;
}

/*
先序遍历二叉树
*/
void PreTraverseBTree(struct BTNode *pT)
{
    /*
        先访问根节点
        再先序访问左子树
        再先序访问右子树
    */
    if (NULL != pT) //如果不加的话，当pT左右子树为空，空没有data域，会报错
    {
        printf("%c\n", pT->data);

        if (NULL != pT->pLchild)
        {
            PreTraverseBTree(pT->pLchild); // pT->pLchild可以代表整个左子树
        }

        if (NULL != pT->pRchild)
        {
            PreTraverseBTree(pT->pRchild); // pT->pLchild可以代表整个右子树
        }
    }
}

/*
中序遍历二叉树
*/
void InTraverseBTree(struct BTNode *pT)
{
    /*
        先中序访问左子树
        再访问根节点
        再先序访问右子树
    */
    if (NULL != pT) //如果不加的话，当pT左右子树为空，空没有data域，会报错
    {
        if (NULL != pT->pLchild)
        {
            InTraverseBTree(pT->pLchild); // pT->pLchild可以代表整个左子树
        }

        printf("%c\n", pT->data);

        if (NULL != pT->pRchild)
        {
            InTraverseBTree(pT->pRchild); // pT->pLchild可以代表整个右子树
        }
    }
}

/*
后序遍历二叉树
*/
void PostTraverseBTree(struct BTNode *pT)
{
    /*
        先后序访问左子树
        再后序访问右子树
        再访问根节点
    */
    if (NULL != pT) //如果不加的话，当pT左右子树为空，空没有data域，会报错
    {
        if (NULL != pT->pLchild)
        {
            PostTraverseBTree(pT->pLchild); // pT->pLchild可以代表整个左子树
        }

        if (NULL != pT->pRchild)
        {
            PostTraverseBTree(pT->pRchild); // pT->pLchild可以代表整个右子树
        }

        printf("%c\n", pT->data);
    }
}
